package main

import "fmt"

func solution(n int, a, b []int) int {
    const mod = 1e9 + 7

    // 扩展 a 和 b，使索引从 1 开始（长度为 n+1）
    aa := make([]int, n+1)
    bb := make([]int, n+1)

    for i := 1; i <= n; i++ {
        aa[i] = a[i-1] % 3
        bb[i] = b[i-1] % 3
    }

    // dp[i][j] 表示前 i 个位置，总和模 3 等于 j 的方案数
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, 3)
    }

    // 初始状态
    f[0][0] = 1

    // 动态规划转移
    for i := 1; i <= n; i++ {
        for j := 0; j < 3; j++ {
            prev1 := (j + 3 - aa[i]) % 3
            prev2 := (j + 3 - bb[i]) % 3
            f[i][j] = (f[i-1][prev1] + f[i-1][prev2]) % mod
        }
    }

    return f[n][0]
}

func main() {
    // 测试用例
    fmt.Println(solution(3, []int{1, 2, 3}, []int{2, 3, 2}) == 3)
    fmt.Println(solution(4, []int{3, 1, 2, 4}, []int{1, 2, 3, 1}) == 6)
    fmt.Println(solution(5, []int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}) == 32)
}